#leetcode题目30：串联所有单词的子串
#难度：困难
#时间复杂度：O(n)
#空间复杂度：O(1)
#方法：滑动窗口

#来源于第二个视频合集
from typing import List
import collections
class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        cnt,word_len=len(words),len(words[0])
        i,j=0,cnt*word_len-1
        ans=[]

        check=collections.Counter(words)
        while j<len(s):
            ss=s[i:j+1]
            tmp=[]
            for k in range(0,len(ss),word_len):
                tmp.append(ss[k:k+word_len])
            if collections.Counter(tmp)==check:
                ans.append(i)

            i+=1
            j+=1
        return ans

#测试数据
s = "barfoothefoobarman"
words = ["foo","bar"]
#预期输出：[0,9]
solution=Solution()
print(solution.findSubstring(s,words))

s = "wordgoodgoodgoodbestword"
words = ["word","good","best","word"]
#预期输出：[]
solution=Solution()
print(solution.findSubstring(s,words))

s = "barfoofoobarthefoobarman"
words = ["bar","foo","the"]
#预期输出：[6,9,12]
solution=Solution()
print(solution.findSubstring(s,words))